import collections
import heapq


class Solution(object):
    def reachableNodes(self, edges, maxMoves, n):
        d = collections.defaultdict(dict)
        for u, v, t in edges:
            d[u][v] = t + 1
            d[v][u] = t + 1
        dist = [-1] * n
        dist[0] = 0
        st = []
        for v in d[0]:
            if d[0][v] <= maxMoves:
                heapq.heappush(st, [d[0][v], v])
        while st:
            t, node = heapq.heappop(st)
            if dist[node] == -1:
                dist[node] = t
                for v in d[node]:
                    if t + d[node][v] <= maxMoves:
                        heapq.heappush(st, [t + d[node][v], v])
        ans = 0
        for p in dist:
            if p >= 0:
                ans += 1
        for u, v, t in edges:
            c = 0
            if dist[u] >= 0:
                c += min(t, maxMoves - dist[u])
            if dist[v] >= 0:
                c += min(t, maxMoves - dist[v])
            ans += min(c, t)
        return ans


data = Solution()
# edges = [[0, 1, 10], [0, 2, 1], [1, 2, 2]]
# maxMoves = 6
# n = 3
# print(data.reachableNodes(edges, maxMoves, n))
edges = [[0, 3, 8], [0, 1, 4], [2, 4, 3], [1, 2, 0], [1, 3, 9], [0, 4, 7], [3, 4, 9], [1, 4, 4], [0, 2, 7], [2, 3, 1]]
maxMoves = 8
n = 5
print(data.reachableNodes(edges, maxMoves, n))
